#ifndef LinkedListGeneric_h__
#define LinkedListGeneric_h__


/*
===============================================================================

Linked list template (Generic)
    double linked, contain T value, std::list<T> usage
===============================================================================
*/

namespace inf {

	// ==============================================================================
	//! ListNodeGeneric for the LinkedListGeneric
	// ==============================================================================
	template<class T>
	class ListNodeGeneric {
	private:
		ListNodeGeneric<T> *prev;	//!< The previous node
		ListNodeGeneric<T> *next;	//!< The next node
		template<class> friend class LinkedListGeneric;

	public:
		// ==============================================================================
		//! Gets the next node
		//!
		//! @return	The node, NULL if this is the last node
		// ==============================================================================
		ListNodeGeneric<T> *get_next( void ) const { return next; }

		// ==============================================================================
		//! Gets the previous node
		//!
		//! @return	The node, NULL if this is the first node
		// ==============================================================================
		ListNodeGeneric<T> *get_prev( void ) const { return prev; }

		T		value;	//!< The value
	};

	// ==============================================================================
	//! Linked list Generic
	// ==============================================================================
	template<class T>
	class LinkedListGeneric {
	public:
		// ==============================================================================
		//! Default constructor
		// ==============================================================================
		LinkedListGeneric();

		// ==============================================================================
		//! copy Constructor
		//!
		//! @param	other	The list to copy from
		// ==============================================================================
		LinkedListGeneric( const LinkedListGeneric<T> &other );

		// ==============================================================================
		//! Destructor
		// ==============================================================================
		~LinkedListGeneric();

		typedef ListNodeGeneric<T> nodeType; //!< The node type

		// ==============================================================================
		//! Definition for a comparision function without extra parameters
		// ==============================================================================
		typedef int ( *cmpFunc_t )( const T &a, const T &b );

		// ==============================================================================
		//! Definition for a comparision function with extra parameters
		// ==============================================================================
		typedef int ( *cmpFuncEx_t )( const T &a, const T &b, void *param );

		// ==============================================================================
		//! clear all entries
		// ==============================================================================
		void		clear( void );

		// ==============================================================================
		//! Checks to see if list is empty
		//!
		//! @return	true if empty, false if not
		// ==============================================================================
		bool		empty( void ) const;

		// ==============================================================================
		//! get the number of entries
		//!
		//! @return	The current number of entries
		// ==============================================================================
		int			size( void ) const;

		// ==============================================================================
		//! add a new value to the start of the list
		//!
		//! @param	value	The value to add
		// ==============================================================================
		void		add_to_start( const T &value );

		// ==============================================================================
		//! add a new value to the end of the list
		//!
		//! @param	value	The value to add
		// ==============================================================================
		void		add_to_end( const T &value );

		// ==============================================================================
		//! insert a value before the specified node
		//!
		//! @param	node	The node to insert before ( if NULL it behaves like AddtoStart )
		//! @param	value	The value to insert
		// ==============================================================================
		void		insert_before( nodeType *node, const T &value );

		// ==============================================================================
		//! insert a value after the specified node
		//!
		//! @param	node	The node to insert after ( if NULL it behaves like AddtoEnd )
		//! @param	value	The value to insert
		// ==============================================================================
		void		insert_after( nodeType *node, const T &value );

		// ==============================================================================
		//! create a new node at the specified node
		//!
		//! @param	baseNode	The base node, can be NULL
		//! @param	before		set to true to insert it before the base node,
		//!						otherwise it will be inserted after the base node
		//!
		//! @return	A reference to the new value
		// ==============================================================================
		T &			alloc( nodeType *baseNode=NULL, bool before=false );

		// ==============================================================================
		//! remove a node
		//!
		//! @param	node	The node to remove
		// ==============================================================================
		void		remove( nodeType *node );

		// ==============================================================================
		//! copy data from an existing list
		//!
		//! @param	other	The list to copy from
		// ==============================================================================
		void		copy( const LinkedListGeneric<T> &other );

		// ==============================================================================
		//! find a node by its value
		//!
		//! @param	value	The value
		//!
		//! @return	NULL if the value was not found, otherwise the node
		// ==============================================================================
		nodeType *	find( const T &value ) const;

		// ==============================================================================
		//! find a node by its value's address
		//!
		//! @param	value	The address of the value
		//!
		//! @return	NULL if the value was not found, otherwise the node
		// ==============================================================================
		nodeType *	find_by_address( const T *value ) const;

		// ==============================================================================
		//! sort the list and (optional) remove duplicates
		//!
		//! @param	compare		The comparision function
		//! @param	removeDupes	true to remove duplicates
		// ==============================================================================
		void		sort( cmpFunc_t compare, bool removeDupes );

		// ==============================================================================
		//! sort the list by specifying a parameter and (optional) remove duplicates
		//!
		//! @param	compare		The comparision function
		//! @param	param		The parameter to pass to the comparision function
		//! @param	removeDupes	true to remove duplicates
		// ==============================================================================
		void		sort_ex( cmpFuncEx_t compare, void *param, bool removeDupes );

		// operators
		// ==============================================================================
		//! copy all entries from the other list
		//!
		//! @param	other	The other list
		//!
		//! @return	A reference to this object
		// ==============================================================================
		LinkedListGeneric<T> &operator=( const LinkedListGeneric<T> &other );

		// ==============================================================================
		//! get the first node
		//!
		//! @return	The first node, NULL if empty
		// ==============================================================================
		nodeType *	get_first_node( void ) const { return start; }

		// ==============================================================================
		//! get the last node
		//!
		//! @return	The last node, NULL if empty
		// ==============================================================================
		nodeType *	get_last_node( void ) const { return end; }

	protected:
		int			num;	//!< Number of items
		nodeType *	start;	//!< pointer to the list start
		nodeType *	end;	//!< pointer to the list end

		// ==============================================================================
		//! Comparison callback
		//!
		//! @param	context	A pointer to the CompareData object
		//! @param	a		A pointer to the first object
		//! @param	b		A pointer to the second object
		//!
		//! @return	0 if the objects match, otherwise positive or negative
		// ==============================================================================
		static int	compare_callback( void *context, const void *a, const void *b );

		// ==============================================================================
		//! Comparison callback
		//!
		//! @param	context	A pointer to the CompareDataEx object
		//! @param	a	A pointer to the first object
		//! @param	b	A pointer to the second object
		//!
		//! @return	0 if the objects match, otherwise positive or negative
		// ==============================================================================
		static int	compare_callback_ex( void *context, const void *a, const void *b );

		// ==============================================================================
		//! Comparison data
		// ==============================================================================
		class CompareData {
		public:
			CompareData( cmpFunc_t f ) : func(f) {}

			cmpFunc_t	func;		//!< The normal comparison function
		};

		// ==============================================================================
		//! Comparison data with parameter
		// ==============================================================================
		class CompareDataEx {
		public:
			CompareDataEx( cmpFuncEx_t f, void *p ) : func(f), param(p) {}

			cmpFuncEx_t	func;		//!< The extended comparison function
			void		*param;		//!< The parameter ( for the extended comparison )
		};
	};

	/*
	================
	LinkedListGeneric::LinkedListGeneric
	================
	*/
	template<class T>
	LinkedListGeneric<T>::LinkedListGeneric( void ) {
		start		= NULL;
		end			= NULL;
		num			= 0;
	}

	/*
	================
	LinkedListGeneric::LinkedListGeneric
	================
	*/
	template<class T>
	LinkedListGeneric<T>::LinkedListGeneric( const LinkedListGeneric<T> &other ) {
		start		= NULL;
		end			= NULL;
		copy(other);
	}

	/*
	================
	LinkedListGeneric::~LinkedListGeneric
	================
	*/
	template<class T>
	LinkedListGeneric<T>::~LinkedListGeneric() {
		clear();
	}

	/*
	================
	LinkedListGeneric::clear
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::clear( void ) {
		if ( start ) {
			nodeType *node = start;
			nodeType *nextNode;
			while( node ) {
				nextNode = node->next;
				delete node;
				node = nextNode;
			}
			start = NULL;
			end = NULL;
		}
		num		= 0;
	}

	/*
	================
	LinkedListGeneric::empty

	Checks to see if list is empty
	================
	*/
	template<class T>
	bool LinkedListGeneric<T>::empty( void ) const {
		return num == 0;
	}

	/*
	================
	LinkedListGeneric::size
	================
	*/
	template<class T>
	int LinkedListGeneric<T>::size( void ) const {
		return num;
	}

	/*
	================
	LinkedListGeneric::copy

	clear the list and
	copy all items from the other list.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::copy( const LinkedListGeneric<T> &other ) {
		clear();
		for( nodeType *node = other.start; node != NULL; node = node->next )
			add_to_end(node->value);
	}

	/*
	================
	LinkedListGeneric::operator=

	Synonym for copy
	================
	*/
	template<class T>
	LinkedListGeneric<T> &LinkedListGeneric<T>::operator=( const LinkedListGeneric<T> &other ) {
		copy(other);
		return *this;
	}

	/*
	================
	LinkedListGeneric::add_to_start

	insert an Item to the start of the list.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::add_to_start( const T &value ) {
		alloc( NULL, true ) = value;
	}

	/*
	================
	LinkedListGeneric::add_to_end

	insert an Item to the end of the list.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::add_to_end( const T &value ) {
		alloc() = value;
	}

	/*
	================
	LinkedListGeneric::insert_before

	insert an Item right before the specified one.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::insert_before( nodeType *node, const T &value ) {
		alloc( node, true ) = value;
	}

	/*
	================
	LinkedListGeneric::insert_after

	insert an item right after the specified one.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::insert_after( nodeType *node, const T &value ) {
		alloc( node, false ) = value;
	}

	/*
	================
	LinkedListGeneric::alloc

	allocate an item at the specified position.
	================
	*/
	template<class T>
	T &LinkedListGeneric<T>::alloc( nodeType *baseNode, bool before ) {
		nodeType *newNode = new nodeType;
		if ( start == NULL ) {
			start = end = newNode;
			start->prev = NULL;
			start->next = NULL;
		} else {
			if ( baseNode == NULL )
				baseNode = before ? start : end;

			if ( before ) {
				newNode->prev = baseNode->prev;
				newNode->next = baseNode;
				baseNode->prev = newNode;
				if ( baseNode == start )
					start = newNode;
			} else {
				newNode->prev = baseNode;
				newNode->next = baseNode->next;
				baseNode->next = newNode;
				if ( baseNode == end )
					end = newNode;
			}
		}
		num++;
		return newNode->value;
	}

	/*
	================
	LinkedListGeneric::remove

	Removes an item from the list.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::remove( nodeType *node ) {
		assert( node != NULL );

		if ( node == start ) {
			if ( node == end )
				start = end = NULL;
			else {
				start = node->next;
				start->prev = NULL;
			}
		} else if ( node == end ) {
			end = node->prev;
			end->next = NULL;
		} else {
			node->prev->next = node->next;
			node->next->prev = node->prev;
		}
		delete node;
		num--;
	}

	/*
	================
	LinkedListGeneric::find

	Returns the index of the searched item.
	-1 if no item with this value was found.
	================
	*/
	template<class T>
	ListNodeGeneric<T> *LinkedListGeneric<T>::find( const T &value ) const {
		nodeType *node = start;
		for( int i=0; node != NULL; i++ ) {
			if ( node->value == value )
				return node;
			node = node->next;
		}
		return NULL;
	}

	/*
	================
	LinkedListGeneric::find_by_address

	Returns the index of the searched item.
	-1 if no item with this value was found.
	================
	*/
	template<class T>
	ListNodeGeneric<T> *LinkedListGeneric<T>::find_by_address( const T *value ) const {
		nodeType *node = start;
		for( int i=0; node != NULL; i++ ) {
			if ( &node->value == value )
				return node;
			node = node->next;
		}
		return NULL;
	}

	/*
	================
	LinkedListGeneric::sort

	Sorts the list and removes duplicates.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::sort( cmpFunc_t compare, bool removeDupes ) {
		if ( num < 2 )
			return;

		nodeType **list = new nodeType*[num];
		int i = 0;
		for( nodeType *node=start; node; node=node->next, i++ )
			list[i] = node;

		CompareData cmpData( this, compare );
		quick_sort( list, num, sizeof( nodeType * ), &cmpData, compare_callback );

		for( i=1; i<num; i++ ) {
			list[i]->prev = list[i-1];
			list[i-1]->next = list[i];
		}

		start = list[0];
		end = list[num-1];

		start->prev = NULL;
		end->next = NULL;

		delete[] list;
		list = NULL;

		if ( removeDupes ) {
			for( nodeType *node=start; node->next; node=node->next ) {
				if ( compare( node->value, node->next->value ) == 0 )
					remove( node->next );
			}
		}
	}

	/*
	================
	LinkedListGeneric::sort_ex

	Sorts the list and removes duplicates.
	================
	*/
	template<class T>
	void LinkedListGeneric<T>::sort_ex( cmpFuncEx_t compare, void *param, bool removeDupes ) {
		if ( num < 2 )
			return;

		nodeType **list = new nodeType*[num];
		int i = 0;
		for( nodeType *node=start; node; node=node->next, i++ )
			list[i] = node;

		CompareDataEx cmpData( this, compare, param );
		quick_sort( list, num, sizeof( nodeType * ), &cmpData, compare_callback_ex );

		for( i=1; i<num; i++ ) {
			list[i]->prev = list[i-1];
			list[i-1]->next = list[i];
		}

		start = list[0];
		end = list[num-1];

		start->prev = NULL;
		end->next = NULL;

		delete[] list;
		list = NULL;

		if ( removeDupes ) {
			for( nodeType *node=start; node->next; node=node->next ) {
				if ( compare( node->value, node->next->value ) == 0 )
					remove( node->next );
			}
		}
	}

	/*
	================
	LinkedListGeneric::compare_callback
	================
	*/
	template<class T>
	int LinkedListGeneric<T>::compare_callback( void *context, const void *a, const void *b ) {
		const nodeType *pa = *(const nodeType **)a;
		const nodeType *pb = *(const nodeType **)b;
		CompareData *cmpData = reinterpret_cast<CompareData *>(context);
		return cmpData->func( pa->value, pb->value );
	}

	/*
	================
	LinkedListGeneric::compare_callback_ex
	================
	*/
	template<class T>
	int LinkedListGeneric<T>::compare_callback_ex( void *context, const void *a, const void *b ) {
		const nodeType *pa = *(const nodeType **)a;
		const nodeType *pb = *(const nodeType **)b;
		CompareDataEx *cmpData = reinterpret_cast<CompareDataEx *>(context);
		return cmpData->func( pa->value, pb->value, cmpData->param );
	}

}   // ::inf

#endif // LinkedListGeneric_h__
